class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1) return nums[0];
        if(n==2) return max(nums[0],nums[1]);
        //     就是让它环不了 到n-2是 ，0已经打完，无法循环，     n-1 和1也是
        return max(nums[0]+getMax(nums,2,n-2),getMax(nums,1,n-1));
    }
    int getMax(vector<int>& nums,int left,int right)
    {
        int n=nums.size();
        vector<int> f(n);   //f[i] 偷
        vector<int> g(n);   //g[i] 不偷

        //初始化
        f[left]=nums[left],g[left]=0;
        //填表
        for(int i=left+1;i<=right;i++)
        {
            f[i]=nums[i]+g[i-1];        //i处偷的+i-1处不偷的
            g[i]=max(g[i-1],f[i-1]);    //i-1处不偷的+i-1处偷的
        }
        //返回n-1处偷或者n-1处不偷的max
        return max(f[right],g[right]);
    }
};